// String.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include <array>
#include <string>
#include <iostream>

using namespace std;

bool isMatch(string::const_iterator start, string::const_iterator end,
             string::const_iterator expressionStart, string::const_iterator expressionEnd)
{
    while (expressionStart != expressionEnd && start != end)
    {
        if (*expressionStart == *start || *expressionStart == '.')
        {
            ++expressionStart;
            ++start;
            continue;
        }
        else if (*expressionStart == '*')
        {
            ++expressionStart;
            while (start != end)
            {
                if (isMatch(start, end, expressionStart, expressionEnd))
                {
                    return true;
                }
                else
                {
                    ++start;
                }
            }
            break;
        }
        else
        {
            return false;
        }
    }
    return expressionStart == expressionEnd && start == end;
}

bool isMatch(string const& str, string const& expression)
{
    return isMatch(str.begin(), str.end(), expression.begin(), expression.end());
}

void testRegularExpression()
{
    //Implement regular expression matching with support for '.' and '*'.
    //'.' Matches any single character. '*' Matches zero or more of the preceding element.
    //The matching should cover the entire input string (not partial).
    struct TestData
    {
        string _str;
        string _expression;
        bool _match;
    };

    array<TestData, 7> data = {{
        {"aa","a", false},
        {"aa","aa", true},
        {"aaa","aa", false},
        {"aa", "a*", true},
        {"aa", ".*", true},
        {"ab", ".*", true},
        {"aab", "c*a*b", true}}};

    for (int i = 0; i < data.size(); ++i)
    {
        if (isMatch(data[i]._str, data[i]._expression) != data[i]._match)
        {
            throw runtime_error("testRegularExpression is failes.");
        }
    }
}

int _tmain(int argc, _TCHAR* argv[])
{
    testRegularExpression();
    return 0;
}

